package tencent;

import java.util.Arrays;

/**
 * 手撕快速排序
 *
 * @Author Jun jie Yi
 * 2022/4/26 20:23
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 4, 6, 9, 11, 43, 65, 11, 23};
        quickSort(0, arr.length - 1, arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int l, int r, int[] arr) {
        int m = arr[l];
        int ql = l, qr = r;//记录原始位置
        while (l < r) {
            while (m < arr[r] && l < r) r--;
            if (l < r) arr[l++] = arr[r];
            while (arr[l] < m && l < r) l++;
            if (l < r) arr[r--] = arr[l];
        }
        arr[l] = m;
        if (ql < l) quickSort(ql, l - 1, arr);
        if (qr > l) quickSort(l + 1, qr, arr);
    }
}
